home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / GenericKeyedHeap.h,v < prev    next >
Text File  |  1988-10-12  |  4KB  |  160 lines
  1. head     1.1;
  2. access   ;
  3. symbols  ;
  4. locks    grunwald:1.1; strict;
  5. comment  @ * @;
  6.  
  7.  
  8. 1.1
  9. date     88.09.18.16.42.06;  author grunwald;  state Exp;
  10. branches ;
  11. next     ;
  12.  
  13.  
  14. desc
  15. @@
  16.  
  17.  
  18.  
  19. 1.1
  20. log
  21. @Initial revision
  22. @
  23. text
  24. @//
  25. // Define the following things:
  26. //    HEAP_NAME    -- the name of the heap type
  27. //    HEAP_INDEX    -- the index type; defaults to unsigned short
  28. //    HEAP_KEY    -- the key type; defaults to double
  29. //    HEAP_ITEM    -- the type name for an item; should be typedefed
  30. //    HEAP_INDEX_NULL    -- the null value for the heap index; defaults to 65535
  31. //    HEAP_BASE_CLASS    -- the base class for the new heap
  32. //
  33.  
  34. #include "Awesime.h"
  35. #include "Generic.h"
  36.  
  37. #ifndef HEAP_INDEX
  38. #define HEAP_INDEX unsigned short
  39. #endif
  40.  
  41. #ifndef HEAP_INDEX_NULL
  42. #define HEAP_INDEX_NULL 0xffff
  43. #endif
  44.  
  45. #ifndef HEAP_KEY
  46. #define HEAP_KEY double
  47. #endif
  48.  
  49. #ifndef HEAP_BASE_CLASS
  50. #define HEAP_BASE_CLASS public Awesime
  51. #endif
  52.  
  53. typedef HEAP_ITEM GENERIC2(HEAP_NAME,Item);
  54. typedef HEAP_KEY GENERIC2(HEAP_NAME,Key);
  55. typedef HEAP_INDEX GENERIC2(HEAP_NAME,Index);
  56.  
  57. extern const GENERIC2(HEAP_NAME,Index) GENERIC2(HEAP_NAME,Null);
  58.  
  59. typedef struct {
  60.     GENERIC2(HEAP_NAME,Key) key;
  61.     GENERIC2(HEAP_NAME,Item) item;
  62.     GENERIC2(HEAP_NAME,Index) sibling;
  63.     GENERIC2(HEAP_NAME,Index) children;
  64. } GENERIC2(HEAP_NAME,Record);
  65.  
  66. class HEAP_NAME : HEAP_BASE_CLASS {
  67.  
  68.     GENERIC2(HEAP_NAME,Record) *storage;
  69.     char *pValid;
  70.     int elements;
  71.     GENERIC2(HEAP_NAME,Index) allocatedSize;
  72.     GENERIC2(HEAP_NAME,Index) freelist;
  73.     GENERIC2(HEAP_NAME,Index) root;
  74.  
  75.     void makeRoom(int atLeast);
  76.  
  77.     GENERIC2(HEAP_NAME,Index) makeChild(GENERIC2(HEAP_NAME,Index) a, GENERIC2(HEAP_NAME,Index) b);
  78.  
  79.     inline GENERIC2(HEAP_NAME,Index) getCell() {
  80.     if (freelist == GENERIC2(HEAP_NAME,Null)) {
  81.         makeRoom(0);
  82.     }
  83.     GENERIC2(HEAP_NAME,Index) cell = freelist;
  84.     pValid[freelist] = 1;
  85.     freelist = storage[freelist].sibling;
  86.     elements++;
  87.     return(cell);
  88.     }
  89.  
  90.     inline void returnCell(GENERIC2(HEAP_NAME,Index) cell) {
  91.     storage[cell].sibling = freelist;
  92.     pValid[cell] = 0;
  93.     freelist = cell;
  94.     elements--;
  95.     }
  96.  
  97. public:
  98.     HEAP_NAME(int length = 0, bool xdebug = 0);
  99.  
  100.     void add(GENERIC2(HEAP_NAME,Key) *key, GENERIC2(HEAP_NAME,Item) *item);
  101.  
  102.     bool remove(GENERIC2(HEAP_NAME,Key) *key,
  103.         GENERIC2(HEAP_NAME,Item) *removed);
  104.  
  105.     
  106.     //
  107.     //    The next four members allow you to search a HEAP_NAME and mark
  108.     //    items as invalid. 
  109.     //
  110.     //    doStart initilizes the index and returns the first item in the list.
  111.     //    doNext moves to the next item and returns that item.
  112.     //    Both return a bool indicating whether the value in item has any
  113.     //    meaning. When bool=FALSE, you've searched everything.
  114.     //  Call doDone at the end to insure compatibility with subclasses.
  115.     //
  116.  
  117.     virtual bool doStart( GENERIC2(HEAP_NAME,Index) &index);
  118.     virtual bool doDelete(GENERIC2(HEAP_NAME,Index) &index);
  119.     virtual bool doNext( GENERIC2(HEAP_NAME,Index) &index);
  120.     virtual void doDone();
  121.  
  122.     inline GENERIC2(HEAP_NAME,Index) minItem() {
  123.     return(root);
  124.     };
  125.  
  126.     inline bool valid(GENERIC2(HEAP_NAME,Index) index) {
  127.     return ( pValid[index] );
  128.     }
  129.  
  130.     inline GENERIC2(HEAP_NAME,Key) & key(GENERIC2(HEAP_NAME,Index) i) {
  131.     return( storage[i].key );
  132.     }
  133.  
  134.     inline GENERIC2(HEAP_NAME,Item) & item(GENERIC2(HEAP_NAME,Index) i) {
  135.     return( storage[i].item );
  136.     }
  137.  
  138.     inline GENERIC2(HEAP_NAME,Index) maxIndex() {
  139.     return(allocatedSize);
  140.     }
  141.  
  142.     inline bool isEmpty() {
  143.     return(elements <= 0);
  144.     }
  145.  
  146.     inline unsigned int size() {
  147.     return(elements);
  148.     }
  149.  
  150.     virtual void classPrintOn(ostream& s);
  151. };
  152.  
  153. #undef HEAP_NAME
  154. #undef HEAP_ITEM
  155. #undef HEAP_KEY
  156. #undef HEAP_INDEX
  157. #undef HEAP_BASE_CLASS
  158.  
  159. @
  160.